package zuo.from0516.other.day06;

import java.util.HashMap;

/**
 * Q105:从前序和中序遍历中构造二叉树
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
 * inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
public class Code05_BuildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 ||inorder.length ==0 || preorder.length != inorder.length){
            return null;
        }
        HashMap<Integer, Integer> valueIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            valueIndexMap.put(inorder[i], i);
        }
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1,valueIndexMap);
    }

    public TreeNode build(int[] pre,int L1,int R1, int[] in,int L2,int R2,HashMap<Integer, Integer> valueIndexMap){
        if(L1>R1){
            return null;
        }
        TreeNode head = new TreeNode(pre[L1],null,null);
        if(L1==R1){
            return head;
        }
        int find = valueIndexMap.get(pre[L1]);
        head.left = build(pre,L1+1,L1+find-L2,in,L2,find-1,valueIndexMap);
        head.right = build(pre,L1+find-L2+1,R1,in,find+1,R2,valueIndexMap);
        return head;
    }
}
